package datastructure.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Given a string, find the length of the longest substring without repeating characters.
 * For example, the longest substring without repeating letters for “abcabcbb” is “abc”, 
 * which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
 * 
 * @author Lei
 */
public class LongestSubstringWithoutRepeatingCharacters {
    
    public static void longestSubstringWithoutRepeatingCharacters(String inputString) {
        char[] chars = inputString.toCharArray();
        Set<String> set = new HashSet<String>();
        int maxLength = 0;
        int curLength = 0;
        int endIndex = 0;
        for (int i = 0; i < chars.length; i++) {
            if (!set.contains(String.valueOf(chars[i]))) {
                set.add(String.valueOf(chars[i]));
                curLength++;
            }
            else {
                if (curLength > maxLength) {
                    maxLength = curLength;
                    endIndex = i;
                    curLength = 0;
                }
            }
        }
        
        System.out.println("the max length is : " + maxLength);
        System.out.println("the max string is : " + inputString.substring(endIndex - maxLength, endIndex));
        
    }
    
    public static void main(String[] args) {
        
        LongestSubstringWithoutRepeatingCharacters.longestSubstringWithoutRepeatingCharacters("abcabcbb");
        System.out.println("");
         LongestSubstringWithoutRepeatingCharacters.longestSubstringWithoutRepeatingCharacters("bbadzdb");
    }
}
